package sort;


public class QuickSort {
    public static <E extends Comparable<E>> E[] sort(E[] array) {
        if (array.length <= 1) {
            return array;
        }
        int low = 0;
        int high = array.length - 1;
        // 哨兵
        int flagIndex = 0;
        E flagValue = array[0];

        while (low != high) {
            while (high > low) {
                if (array[high].compareTo(flagValue) < 0) {
                    array[flagIndex] = array[high];
                    flagIndex = high;
                    break;
                }
                high--;
            }

            while (low < high) {
                if (array[low].compareTo(flagValue) > 0) {
                    array[flagIndex] = array[low];
                    flagIndex = low;
                    break;
                }
                low++;
            }
        }
        array[high] = flagValue;     
        E[] tmp = (E[]) new Comparable[high + 1];
        System.arraycopy(array, 0, tmp, 0, high + 1);
        tmp = sort(tmp);
        for (int i = 0; i < tmp.length; i++) {
            array[i] = tmp[i];
        }
        if (high != array.length - 1){
            tmp = (E[]) new Comparable[array.length - high - 1]; 
            System.arraycopy(array, high + 1, tmp, 0, array.length - high - 1);
            tmp = sort(tmp);
            for (int i = 0; i < tmp.length; i++) {
                array[high + i + 1] = tmp[i];
            }
        }

        return array;
    }
}